package internal.exchange;

/**
 * @描述：传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者),从而使排序趟数几乎减少了一半
 * @作者：hongxingfan
 * @时间：2014年9月5日 上午9:38:26
 */
public class BubbleSort_2 {

    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        // 冒泡排序
        bubbleSort_2(datas);

        // 输出结果
        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    // 改进后的冒泡排序
    public static void bubbleSort_2(int[] datas) {
        int num = 0; // 比较的次数；这里是5次；比BubbleSort_1的8小
        int high = datas.length - 1;
        int low = 0;

        // 向两边赶数据，两个for循环顺序执行
        while (low < high) {
            num++;
            for (int i = 1; i <= high; i++) {
                if (datas[i - 1] > datas[i]) {
                    int tmp = datas[i];
                    datas[i] = datas[i - 1];
                    datas[i - 1] = tmp;
                }
            }
            high--;
            for (int i = high - 1; i >= low; i--) {
                if (datas[i + 1] < datas[i]) {
                    int tmp = datas[i];
                    datas[i] = datas[i + 1];
                    datas[i + 1] = tmp;
                }
            }
            low++;
        }
        System.out.println(num);
    }
}
